package Review;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Test05 {
//    public int[] sortArray(int[] nums)
//    {
//        qsort(nums, 0, nums.length - 1);
//        return nums;
//    }
//    public void qsort(int[] nums, int l, int r)
//    {
//        if(l >= r) return;
//        // 数组分三块
//        int key = nums[new Random().nextInt(r - l + 1) + l];
//        int left = l - 1, right = r + 1, i = l;
//        while(i < right)
//        {
//            if(nums[i] < key) swap(nums, ++left, i++);
//            else if(nums[i] == key) i++;
//            else swap(nums, --right, i);
//        }
//        // [l, left] [left + 1, right - 1] [rigth, r]
//        qsort(nums, l, left);
//        qsort(nums, right, r);
//    }
    public void swap(int[] nums, int i, int j)
    {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
//    public int minNumberOfFrogs(String c)
//    {
//        char[] croakOfFrogs = c.toCharArray();
//        String t = "croak";
//        int n = t.length();
//        int[] hash = new int[n]; // 数组模拟哈希表
//        Map<Character, Integer> index = new HashMap<>(); // [x, x这个字符对应的下标
//        for(int i = 0; i < n; i++)
//            index.put(t.charAt(i), i);
//        for(char ch : croakOfFrogs)
//        {
//            if(ch == t.charAt(0))
//            {
//                if(hash[n - 1] != 0) hash[n - 1]--;
//                hash[0]++;
//            }
//            else
//            {
//                int i = index.get(ch);
//                if(hash[i - 1] == 0) return -1;
//                hash[i - 1]--; hash[i]++;
//            }
//        }
//        for(int i = 0; i < n - 1; i++)
//            if(hash[i] != 0)
//                return -1;
//
//        return hash[n - 1];
//    }
    public String countAndSay(int n)
    {
        String ret = "1";
        for(int i = 1; i < n; i++) // 解释 n - 1 次 ret 即可
        {
            StringBuilder tmp = new StringBuilder();
            int len = ret.length();
            for(int left = 0, right = 0; right < len; )
            {
                while(right < len && ret.charAt(left) == ret.charAt(right)) right++;
                tmp.append(Integer.toString(right - left));
                tmp.append(ret.charAt(left));
                left = right;
            }
            ret = tmp.toString();
        }
        return ret;
    }
    public String convert(String s, int numRows)
    {
        // 处理⼀下边界情况
        if(numRows == 1) return s;
        int d = 2 * numRows - 2, n = s.length();
        StringBuilder ret = new StringBuilder();
        // 1. 处理第⼀⾏
        for(int i = 0; i < n; i += d)
            ret.append(s.charAt(i));
        // 2. 处理中间⾏
        for(int k = 1; k < numRows - 1; k++) // 依次枚举中间⾏
        {
            for(int i = k, j = d - i; i < n || j < n; i += d, j += d)
            {
                if(i < n) ret.append(s.charAt(i));
                if(j < n) ret.append(s.charAt(j));
            }
        }

        // 3. 处理最后⼀⾏
        for(int i = numRows - 1; i < n; i += d)
            ret.append(s.charAt(i));
        return ret.toString();
    }
    public static void main(String[] args) {
        int[] arr = new int[]{1,1,-1,1,-1,1};
        int ret = subarraySum(arr,2);
        System.out.println(ret);
    }
    public static int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        //下面表示正好前i个前缀和为k
        map.put(0,1);
        int sum = 0;
        int ret = 0;
        for(int i = 0;i<nums.length;i++){
            sum+=nums[i];
            ret+=map.getOrDefault(sum-k,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ret;
    }
    //在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if(nums.length == 0) return ret;
        //寻找左端点
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        //结束循环的条件是left与right重合,因此下面写right下标也可以
        if(nums[left] == target) ret[0] = left;
        //寻找右端点
        //其实我们从上面找到的左端点进行遍历也可以
        //但是为了保证代码的完整性质,我们这样写了
        //因为后面要用到左右端点的模板
        //我们把下面的一行代码注释了也正确
        left = 0;
        right = nums.length - 1;
        while(left < right){
            int mid = left + (right - left + 1)/2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;

        }
        if(nums[left] == target) ret[1] = left;
        return ret;
    }
    //翻转链表
//    public ListNode reverseList(ListNode head) {
//        if(head == null || head.next == null) return head;
//        ListNode newHead = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return newHead;
//    }
    //盛更多水的容器
    public int maxArea(int[] height) {
        int max = 0;
        int left = 0;
        int right = height.length - 1;
        while(left < right){
            int temp = (right - left) * (height[left] < height[right] ? height[left++]: height[right--]);
            if(temp > max){
                max = temp;
            }
            // if()
        }
        return max;
    }
    //快乐数
    public static int func(int n){
        int ret = 0;
        while(n > 0){
            int t = n % 10;
            ret+=(t*t);
            n/=10;
        }
        return ret;

    }
    public boolean isHappy(int n) {
        // int m
        //快慢指针?
        int slow = n;
        int fast = func(n);
        while(slow != fast){
            slow = func(slow);
            fast = func(func(fast));
        }
        return slow == 1;
    }
    //01背包问题
    public static void main11(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        for(int i = 1;i<=n;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }
        int[][] f = new int[n+1][m+1];
        for(int i = 1 ;i<=n;i++){
            for(int j = m;j>=0;j--){
                if(j < v[i]) f[i][j] = f[i-1][j];
                else f[i][j] = Math.max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
        }
        System.out.println(f[n][m]);
    }
    //将x减到0的最小操作数
    public int minOperations(int[] nums, int x) {
        int count = 0;
        int sum = 0;
        for(int m:nums){
            sum+=m;
        }
        int tar = sum - x;
        //下面的条件必须处理,x可能大于所有的取值和
        if(tar < 0) return -1;
        //这次的思想是正难则反 , 需要借助三方变量
        int tmp = 0;
        int ret = -1;
        for(int l = 0,r = 0;r < nums.length;r++){
            //进窗口
            // int record = 0;
            tmp+=nums[r];
            //出窗口
            while(tmp > tar){
                tmp-=nums[l++];
            }
            if(tar == tmp){
                ret = Math.max(ret,r-l+1);
            }
        }
        if(ret == -1) return -1;
        else return nums.length - ret;
    }
    //验证二叉搜索树
//    long pre = Long.MIN_VALUE;
//    public boolean isValidBST(TreeNode root) {
//        if(root == null) return true;
//        boolean left = isValidBST(root.left);
//        boolean cur = false;
//        if(root.val > pre) cur = true;
//        pre = root.val;
//        boolean right = isValidBST(root.right);
//        return left && cur && right;
//    }
    //两两交换链表的节点(递归)
//    public ListNode swapPairs(ListNode head) {
//        if(head == null || head.next == null) return head;
//        ListNode temp = swapPairs(head.next.next);
//        ListNode ret = head.next;
//        // head.next = ret;
//        // ret.next = head;
//        ret.next = head;
//        head.next = temp;
//        return ret;
//    }
    //创建一个备忘录
    int[] memo = new int[50];
    public int fib(int n) {
        Arrays.fill(memo,-1);
        return dfs(n);
    }
    int dfs(int n){
        if(memo[n] != -1) return memo[n];
        if(n == 0 || n == 1) {
            memo[n] = n;
            return n;
        }
        memo[n] = dfs(n-1) + dfs(n-2);
        return memo[n];

    }
    public static void main13(String[] args) {
        int[] arr= new int[50];
        Arrays.fill(arr,-1);
        System.out.println(Arrays.toString(arr));
    }
    //通过汉诺塔问题认识递归
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }
    public void dfs(List<Integer> A, List<Integer> B, List<Integer> C,int n){
        //递归出口 , 一定要有return
        if(n == 1){
            C.add(A.remove(A.size()-1));
            return;
        }
        //先把A上的所有盘子借助C柱子搞到
        dfs(A,C,B,n-1);
        C.add(A.remove(A.size()-1));
        //此时所有的盘子在B上
        dfs(B,A,C,n-1);
    }
    //移动零
    public void moveZeroes(int[] nums) {
        //划分成三个区域
        //非0区域
        //0区域
        //待处理区域
        int des = -1 ;
        int cur = 0;
        for(;cur < nums.length;cur++){
            if(nums[cur] != 0){
                des++;
                int temp = nums[des];
                nums[des] = nums[cur];
                nums[cur] = temp;
            }
        }
    }
    public static void main3(String[] args) {
        String str = "1230";
        char[] ch = str.toCharArray();
    }
    //三步问题
    public int waysToStep(int n) {
        if(n == 0) return 1;
        if(n == 1) return 1;
        if(n == 2) return 2;
        int[] f = new int[n+1];
        f[0] = 1;
        f[1] = 1;
        f[2] = 2;
        int MOD = (int)1e9 + 7;
        for(int i = 3;i<=n;i++){
            f[i] = ((f[i-1] + f[i-2])%MOD + f[i-3])%MOD;
        }
        return f[n];
    }
    //使用最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] f = new int[n+1];
        f[0] = 0;
        f[1] = 0;
        for(int i = 2;i<=n;i++){
            f[i] = Math.min(f[i-1] + cost[i-1],f[i-2] + cost[i-2]);
        }
        return f[n];
    }
}
